import collections


class Solution(object):
    def mostVisitedPattern(self, username, timestamp, website):
        """
        :type username: List[str]
        :type timestamp: List[int]
        :type website: List[str]
        :rtype: List[str]
        """

        def search(user, i, k, n):
            if k == 0:
                score_user[user].add(tuple(now_list))
            else:
                for j in range(i, n - k + 1):
                    now_list.append(d[user][j][1])
                    search(user, j + 1, k - 1, n)
                    now_list.pop()

        d = collections.defaultdict(list)
        n = len(username)
        score = collections.defaultdict(int)
        score_user = collections.defaultdict(set)
        for i in range(n):
            d[username[i]].append((timestamp[i], website[i]))
        now_list = []
        for user in d:
            d[user].sort()
            n = len(d[user])
            if n >= 3:
                search(user, 0, 3, n)
        for user in score_user:
            for item in score_user[user]:
                score[item] += 1
        max_score = -1
        for key in score:
            if score[key] > max_score:
                max_score = score[key]
                max_set = {key}
            else:
                if score[key] == max_score:
                    max_set.add(key)
        return list(min(max_set))


data = Solution()
username = ["joe", "joe", "joe", "james", "james", "james", "james", "mary", "mary", "mary"]
timestamp = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
website = ["home", "about", "career", "home", "cart", "maps", "home", "home", "about", "career"]
print(data.mostVisitedPattern(username, timestamp, website))
username = ["joe", "joe", "joe", "james", "james", "james", "james", "mary", "mary", "mary"]
timestamp = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
website = ["home", "about", "career", "home", "cart", "maps", "home", "home", "about", "career"]
print(data.mostVisitedPattern(username, timestamp, website))
username = ["ua", "ua", "ua", "ub", "ub", "ub"]
timestamp = [1, 2, 3, 4, 5, 6]
website = ["a", "b", "a", "a", "b", "c"]
print(data.mostVisitedPattern(username, timestamp, website))
username = ["h", "eiy", "cq", "h", "cq", "txldsscx", "cq", "txldsscx", "h", "cq", "cq"]
timestamp = [527896567, 334462937, 517687281, 134127993, 859112386, 159548699, 51100299, 444082139, 926837079,
             317455832, 411747930]
website = ["hibympufi", "hibympufi", "hibympufi", "hibympufi", "hibympufi", "hibympufi", "hibympufi", "hibympufi",
           "yljmntrclw", "hibympufi", "yljmntrclw"]
print(data.mostVisitedPattern(username, timestamp, website))
